<?php
require 'UF.php';

class UnionFind1 implements UF
{
    private $ids = [];
    private $size = 0;

    /**
     * 构造函数 初始化并查集
     * UnionFind1 constructor.
     * @param int $size
     */
    public function __construct(int $size)
    {
        $this->size = $size;
        for ($i = 0; $i < $this->size; $i++) {
            $this->ids[$i] = $i;
        }
    }

    public function getSize(int $p, int $q): int
    {
        return $this->size;
    }

    /**
     * 查找元素对应的集合编号
     * @param int $p
     * @return mixed
     */
    private function find(int $p)
    {
        if ($p < 0 && $p >= $this->size) {
            echo "not found";
            exit;
        }
        return $this->ids[$p];
    }

    /**
     * 查看两个元素思否属于一个集合
     * @param int $p
     * @param int $q
     * @return bool
     */
    public function isConnected(int $p, int $q): bool
    {
        return $this->ids[$p] == $this->ids[$q];
    }

    public function unionElements(int $p, int $q): void
    {
        $qId = $this->find($q);
        $pId = $this->find($p);
        if ($pId != $qId) {
            for ($i = 0; $i < $this->size; $i++) {
                if ($this->ids[$i] == $pId) {
                    $this->ids[$i] = $qId;
                }
            }
        }
    }
}

